//
// Created by Semir on 2020/5/24.
//

#include <iostream>
#include <vector>

using namespace std;

int MoreThanHalfNum_Solution(vector<int> numbers) {
    int target = numbers[0];
    int cnt = 1;
    for (int i = 1; i < numbers.size(); i++) {
        if (numbers[i] != target) {
            cnt--;
        } else {
            cnt++;
        }
        if (cnt == 0) {
            target = numbers[i];
            cnt = 1;
        }
    }
    cnt = 0;
    for (int number : numbers) {
        if (number == target) {
            cnt++;
        }
    }
    return cnt > numbers.size() / 2 ? target : 0;
}

int main() {
    vector<int> vec = {1,1,1,2,2,2,2,2,3};
    int res = MoreThanHalfNum_Solution(vec);
    cout << res << endl;
    return 0;
}